#define _CRT_SECURE_NO_WARNINGS 1
#include <string>
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
vector<string> vs;
class Solution {
public:
    void recursion(string& str, map<int, bool> m, int n, string s)
    {
        //cout<<"n="<<n<<"ssize="<<str.size()<<endl;
        if (n >= str.size())
        {
            //cout<<"end"<<" "<<s<<endl;
            vs.push_back(s);
            return;
        }
        for (int i = 0;i < str.size();i++)
        {
            if (m[i] == true) continue;
            auto tmpm = m;
            tmpm[i] = true;
            string tmps = s;
            tmps += str[i];
            //cout<<"n="<<n<<"i="<<i<<" "<<tmps<<endl;
            recursion(str, tmpm, n + 1, tmps);
        }
        return;
    }
    vector<string> Permutation(string str)
    {
        map<int, bool> m;
        for (int i = 0;i < str.size();i++) m[i] = false;
        string s;
        recursion(str, m, 0, s);
        // for(auto& a:vs)
        // {
        //     cout<<a<<endl;
        // }
        set<string> ss;
        for (auto& a : vs)
        {
            ss.insert(a);
        }
        vector<string> ret;
        for (auto& a : ss)
        {
            ret.push_back(a);
        }
        return ret;
    }
};